package main

//#link:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
//参考题解:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/
func main() {

}

var result []string
var letterMap map[string]string = map[string]string{
	"2": "abc",
	"3": "def",
	"4": "ghi",
	"5": "jkl",
	"6": "mno",
	"7": "pqrs",
	"8": "tuv",
	"9": "wxyz",
}

//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
//给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母
func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	result = make([]string, 0)
	backTrace(digits, 0, "")
	return result
}

func backTrace(digits string, index int, path string) {
	if index == len(digits) {
		result = append(result, path)
	} else {
		letter := digits[index]
		letters := letterMap[string(letter)]
		for i := 0; i < len(letters); i++ {
			backTrace(digits, index+1, path+string(letters[i]))
		}
	}
}
